home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / BASE_HAS.H < prev    next >
C/C++ Source or Header  |  1992-08-20  |  10KB  |  220 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 06/06/89 -- Initial design and implementation
  13. // Updated: MBN 06/28/89 -- Added protected set and get current position
  14. // Updated: MBN 09/20/89 -- Added conditional exception handling
  15. // Updated: MBN 09/26/89 -- Added method to return key at current position
  16. // Updated: MBN 10/12/89 -- Changed "current_position" to "curpos" and
  17. //                          added current_position() method for Iterator<Type>
  18. // Updated: VDN 02/21/92 -- New lite version
  19. // Updated: JAM 08/18/92 -- removed DOS specifics, stdized #includes
  20. // Updated: JAM 08/18/92 -- modernized template syntax, remove macro hacks
  21. //                          non-template classes CoolHash_Table=>CoolBase_Hash_Table
  22. // Updated: JAM 08/18/92 -- made *_state typedef a nested typedef "IterState"
  23. //                          as per new Iterator convention
  24. //
  25. // The  Base Hash Table  class implements the  generic hash table functionality
  26. // that is  required  by  the  parameterized  Hash Table class.  The Hash Table
  27. // class is  dynamic in nature.  It's  size (ie. the  number of buckets  in the
  28. // table) is always some prime number. Each bucket holds 8 items. No wholes are
  29. // left in  a bucket; if a  key/value pair is  removed   from  the middle  of a
  30. // bucket, following entries are moved up.  When a hash on  a  key ends up in a
  31. // bucket that is full, the table is enlarged.
  32. //
  33. // The number of buckets currently in the table is  accessed by an index into a
  34. // static table of selected prime  numbers. This static table  contained within
  35. // the  class eliminates the  somewhat expensive  runtime  computation of prime
  36. // numbers.  The table consists of prime numbers  where  the difference between
  37. // any two successive entries gets progressively larger as you move through the
  38. // table.  The specified range of primes results in an  arbitrary limitation of
  39. // 2^22 entries in a single hash table.
  40. //
  41. // The private data section  includes  a pointer to a   byte vector   (that is,
  42. // unsigned char) that  maintains a count  of the number   of  entries in  each
  43. // bucket, a growth ratio that can be used to set a growth rate percentage when
  44. // necessary, an  entry count,  an  index into  the   prime number  table  that
  45. // indicates the number of buckets in the table,  and  a current position union
  46. // that maintains the bucket number and index into the bucket of the  last hash
  47. // operation.
  48. //
  49. // Three different constructors are provided.   The first constructor  takes no
  50. // arguments and  creates a  hash table with  three buckets that  can contain a
  51. // total of 24 items.   The second constructor  accepts an integer argument and
  52. // creates a hash table of some prime number of buckets that  can accomodate at
  53. // least the specified number of items.  Finally, the third constructor takes a
  54. // single argument consisting of a reference to a Hash Table and duplicates its
  55. // size and contents.
  56. //
  57. // The Base Hash Table class implements the notion of a  current position. This
  58. // is useful for  iterating through the table  of hashed values.   The  current
  59. // position is maintained in a union of either a long (used for initialization)
  60. // or in two bit fields.  The first bit field is of length  8 and maintains the
  61. // index of the last item in a bucket.   The  second bit field is of  length 24
  62. // and maintains  the bucket (prime) number last  used.   Methods to reset, and
  63. // move to the next and previous  entries  are provided in  the Base Hash Table
  64. // class.
  65. //
  66. // Methods are provided to to clear all  values from the  table entirely, three
  67. // functions to set the hash,  key compare, and  value compare functions for an
  68. // instance of a hash table, accessor methods to get the bucket and total entry
  69. // count, and a method to set the growth ratio are also available.
  70.  
  71. #ifndef BASE_HASH_TABLEH            // If no Base Hash Table class,
  72. #define BASE_HASH_TABLEH            // define it
  73.  
  74. #ifndef STREAMH            // If the Stream support not yet defined,
  75. #include <iostream.h>        // include the Stream class header file
  76. #define STREAMH
  77. #endif
  78.  
  79. #ifndef MISCELANEOUSH        // If we have not included this file,
  80. #include <misc.h>        // include miscelaneous useful definitions.
  81. #endif
  82.  
  83. #define BUCKET_SIZE 8
  84.  
  85. extern long hash_primes[];
  86.  
  87. // The following preprocessor macros get and set the relative bits in  a 32 bit
  88. // field that represent the  bucket  index,  bucket number, and traversed  bit.
  89. // This is  used instead of a  bit  field because of the non-portability issues
  90. // surrounding bit fields in various C compilers. Also  note that the traversed
  91. // bit macro is defined here, although it is utilized in the Set class.
  92.  
  93. #define BUCKET_INDEX(x) ((x & 0xFF000000L) >> 24)
  94. #define BUCKET_NUMBER(x) (x & 0x007FFFFFL)
  95. #define TRAVERSED(x) ((x & 0x00800000L) >> 23)
  96.  
  97. #define SET_BUCKET_INDEX(x) ((x & 0x000000FFL) << 24)
  98. #define SET_BUCKET_NUMBER(x) (x & 0x007FFFFFL)
  99. #define SET_TRAVERSED(x) ((x & 0x00000001L) << 23)
  100.  
  101. class CoolBase_Hash_Table {                // Base Hash class definition
  102. protected:
  103.   unsigned char* items_in_buckets;        // Count of entries in buckets
  104.   float growth_ratio;                // Growth ratio
  105.   long entry_count;                // Number of entries in table
  106.   long current_bucket;                // Index to number of buckets
  107.   long curpos;                    // BUCKET_NUM*BUCKET_SIZE+INDEX
  108.  
  109.   CoolBase_Hash_Table ();                // Hash table of default size
  110.   CoolBase_Hash_Table (long);                // Hash table for at least size
  111.   CoolBase_Hash_Table (const CoolBase_Hash_Table&);        // Hash table with reference
  112.  
  113.   void ratio_error (float);                 // Raise exception
  114.   void resize_error (const char*, const char*, long); // Raise exception
  115.   void value_error (const char*, const char*);         // Raise exception
  116.   void key_error (const char*, const char*);         // Raise exception
  117.   void remove_error (const char*, const char*);         // Raise exception
  118.  
  119. public:
  120.   typedef long IterState;            // Current position state
  121.  
  122.   ~CoolBase_Hash_Table();                // Destructor
  123.   CoolBase_Hash_Table& operator= (const CoolBase_Hash_Table&);    // Assignment
  124.  
  125.   inline long length () const;            // Return number of entries
  126.   inline long capacity () const;        // Return max number of entries
  127.   inline Boolean is_empty () const;        // Determine empty/nonempty 
  128.   inline long get_bucket_count () const;    // Return number of buckets
  129.   inline void set_ratio (float);        // Set growth ratio
  130.   inline int get_count_in_bucket(long) const;    // Used to return item count
  131.   inline IterState& current_position ();    // Get/set current position
  132.  
  133.   inline void reset ();                // Make current position invalid
  134.   Boolean next ();                // Advance current position by 1
  135.   Boolean prev ();                // Backup current position by 1
  136.   void statistics ();                           // Print Table Statistics
  137.   void clear ();                // Empty the hash table
  138. };
  139.  
  140.  
  141. // Get_bucket_count -- Return number of buckets in hash table
  142. // Input:              this*
  143. // Output:             Number of buckets in hash table           
  144.  
  145. inline long CoolBase_Hash_Table::get_bucket_count () const {
  146.   return hash_primes[this->current_bucket];
  147. }
  148.  
  149.  
  150. // length -- Return number of entries in hash table
  151. // Input:    this*
  152. // Output:   Number of entries in hash table
  153.  
  154. inline long CoolBase_Hash_Table::length () const {
  155.   return this->entry_count;
  156. }
  157.  
  158.  
  159. // current_position () -- Return current position state
  160. // Input:                 None
  161. // Output:                Reference to current position state
  162.  
  163. inline CoolBase_Hash_Table::IterState& CoolBase_Hash_Table::current_position () {
  164.   return this->curpos;
  165. }
  166.  
  167.  
  168. // capacity -- Return maximum number of elements object can hold
  169. // Input:      None
  170. // Output:     Integer value of maximum number of elements
  171.  
  172. inline long CoolBase_Hash_Table::capacity () const {
  173.   return hash_primes[this->current_bucket] * BUCKET_SIZE; //Max number entries
  174. }
  175.  
  176.  
  177. // is_empty -- Return empty status of hash table
  178. // Input:      this*
  179. // Output:     TRUE/FALSE
  180.  
  181. inline Boolean CoolBase_Hash_Table::is_empty () const {
  182.   return this->entry_count == 0;
  183. }
  184.  
  185.  
  186. // set_ratio -- Set the growth ratio
  187. // Input:       this*, growth ratio
  188. // Output:      None
  189.  
  190. inline void CoolBase_Hash_Table::set_ratio (float ratio) {
  191. #if ERROR_CHECKING
  192.   if (ratio < 0.0)                // If invalid ratio
  193.     this->ratio_error (ratio);            // Raise exception
  194. #endif
  195.   this->growth_ratio = ratio;            // Set growth ratio
  196. }
  197.  
  198.  
  199. // get_count_in_bucket -- Return the number of items in specific bucket
  200. // Input:                 Bucket number
  201. // Output:                Number of items in bucket
  202.  
  203. inline int CoolBase_Hash_Table::get_count_in_bucket (long i) const {
  204.   return items_in_buckets[i];
  205. }
  206.  
  207.  
  208. // reset -- Set current position to INVALID
  209. // Input:   this*
  210. // Output:  None
  211.  
  212. inline void CoolBase_Hash_Table::reset () {
  213.   this->curpos = INVALID;            // Invalidate current position
  214. }
  215.  
  216. extern unsigned long sxhash (const char*);    // Calculate hash for string
  217. extern Boolean charP_compare (char* const &, char* const&);// Key compare for char*
  218.  
  219. #endif                        // End of BASE_HASH_TABLEH
  220.